from sys import stdin,argv
from random import randint
from copy import copy

def even(x):
	"""
	>>> print even(42)
	True
	"""
	return x%2 == 0

def odd(x):
	"""
	>>> print odd(43)
	True
	"""
	return x%2 != 0

def check(arr):
	"""
	>>> print check([1,3,5,7])
	True
	>>> print check([2,1,3])
	True
	>>> print check([])
	True
	>>> print check([2,1,4])
	False
	"""
	ev = True
	for x in arr:
		if not ev and even(x):
			return False
		ev = ev and even(x)
	return True

def testing(arr):
	last_even = -1 if odd(arr[0]) else 0
	for i in range(1, len(arr)):
		if even(arr[i]):
			arr[last_even+1], arr[i] = arr[i], arr[last_even+1]
			last_even += 1
	return arr

def official1(arr):
	(i, j) = (0, len(arr)-1)
	while i != j:
		if even(arr[i]):
			i += 1
		else:
			arr[i], arr[j] = arr[j] , arr[i]
			j -= 1
	return arr

def official2(arr):
	i = j = 0
	while i < len(arr):
		if even(arr[i]):
			arr[j], arr[i] = arr[i], arr[j]
			j += 1
		i += 1
	return arr

def official2_bare(arr):
	i = j = 0
	while i < len(arr):
		if odd(arr[i]):
			i += 1
		else:
			arr[j], arr[i] = arr[i], arr[j]
			i += 1
			j += 1
	return arr

def gen(sz, lb, ub):
	"""Generates a list of sz int in [lb, ub]"""
	arr = []
	for i in range(sz+1):
		arr.append(randint(lb, ub))
	return arr


if len(argv)==2:
	import doctest
	doctest.testmod()
	if argv[1].isdigit():
		ct = int(argv[1])
		fails = 0
		for i in range(ct):
			arr = gen(20, -5, 10)
			a = testing(copy(arr))
			b = official1(copy(arr))
			c = official2(copy(arr))
			if not check(a):
				print arr
				print "1", b
				print "2", c
				print "T", a
				fails += 1
		if fails==0:
			print "It looks like the tested algorithm works!"
		else:
			print "Failures:", fails, "/", ct, "tests"
	else:
		print "Please provide a number of tests or no parameter at all."
else:
	arr = map(lambda x: int(x), stdin.readlines())
	print "The first official algorithm says", official1(copy(arr))
	print "The second official algorithm says", official2(copy(arr))
	print "The tested algorithm says", testing(copy(arr))

